#include<bits/stdc++.h>
using namespace std;

template <class T>
class AVLTree {
private:
	struct node {
		T val;
		int cnt,h;
		node *lson;
        node *rson;
		node(const T & _val, node * _lson, node * _rson, int _cnt = 1, int _h = 0) : val(_val), cnt(_cnt), h(_h) {lson = _lson, rson = _rson;}
	};
    node * root;

	int ht(node * p) const {return p == nullptr ? -1 : p -> h;}
	
	void clear(node *& u) {
		if(u == nullptr) return;
		clear(u -> lson);
		clear(u -> rson);
		delete u;
		u = nullptr;
	}
	
	
	void update(node *& u) {
		u -> h = max(ht(u -> lson), ht(u -> rson)) + 1;
	}
	

    void leftrotate(node* &u){
        node *v =u -> lson;
        u -> lson=v -> rson;
        v -> rson= u;
        update(u);
        update(v);
		u = v;
    }

    void rightrotate(node *&u){
        node *v = u -> rson;
        u -> rson= v -> lson;
        v -> lson= u;
        update(u);
        update(v);
		u = v;
    }

	void rotate(node *& u, bool op) {
		node * v = u -> son[op];
		u -> son[op] = v -> son[op^1];
		v -> son[op^1] = u;
		update(u), update(v);
		u = v;
	}
	
	void balance(node *& u){
		if (u == nullptr) return;
		if (ht(u -> lson) - ht(u -> rson) > 1) {
			if(ht(u -> lson -> lson) >= ht(u -> lson -> rson))
				leftrotate(u);
			else
				rightrotate(u -> lson), leftrotate(u);
		}
		else if (ht(u -> rson) - ht(u -> lson) > 1) {
			if(ht(u -> rson -> rson) >= ht(u -> rson -> lson))
				rightrotate(u);
			else
				leftrotate(u -> rson), rightrotate(u);
		}
		update(u);
	}
	
	void insert(const T & val, node *& u) {
		if (u == nullptr) {
			u = new node(val, nullptr, nullptr);
			return;
		}
		if (val < u -> val) insert(val, u -> lson);
		else if (u -> val < val) insert(val, u -> rson);
		else ++u -> cnt;
		
		balance(u);
	}
	
	void vectorprint(vector <T> & v, node * u) {
		if (u == nullptr) return;
		vectorprint(v, u -> lson);
		for (int i = 0; i < u -> cnt; ++i) v.push_back(u -> val);
		vectorprint(v, u -> rson);
	}
	
public:
	AVLTree(){
		root = nullptr;
	}
	~AVLTree() {
		clear(root);
	}
	void insert(const T & val) {
		insert(val, root);
	}
	void vectorprint(vector <T> & data) {
        data.clear();
		vectorprint(data, root);
	}
};

template <class T>
class SplayTree {
private:
	struct node {
		T val;
		int cnt;
		node * fa;
		node * lson;
		node * rson;
		node(const T & _val, node * _fa, node * _lson, node * _rson, int _cnt = 1) : val(_val), cnt(_cnt), fa(_fa) {lson = _lson, rson = _rson;}
	};
	
	// Clear u and the subtree of u.
	void clear(node *& u) {
		if(u == nullptr) return;
		clear(u -> lson);
		clear(u -> rson);
		delete u;
		u = nullptr;
	}
	
	node * root;
	
	void rotate(node *& u) {
		node * v = u -> fa, * r = v -> fa;
		bool op = u == v -> rson;
		u -> fa = r;
		if (r == nullptr) root = u;
		//else r -> son[v == r -> rson] = u;
		else if(v == r -> rson)
			r -> rson = u;
		else r -> lson = u;
		if(op == 1) {
			if(u -> lson != nullptr)
				u -> lson -> fa =v;
			v -> rson = u ->lson;
			v -> fa = u;
			u -> lson = v;
		}
		else {
			if(u -> rson != nullptr)
				u -> rson -> fa =v;
			v -> lson = u ->rson;
			v -> fa = u;
			u -> rson = v;
		}
		// if (u -> son[op ^ 1] != nullptr) u -> son[op ^ 1] -> fa = v;
		// v -> son[op] = u -> son[op ^ 1];
		// v -> fa = u;
		// u -> son[op ^ 1] = v;
	}
	
	void splay(node * u){
		if (u == nullptr) return;
		while (u != root) {
			node * v = u -> fa, * r = v -> fa;
			if (v != root) {
				if ((u == v -> rson) ^ (v == r -> rson)) rotate(u);
				else rotate(v);
			}
			if (u != root) rotate(u);
		}
	}
	
	void insert(const T & val, node *& u, node * f = nullptr) {
		if (u == nullptr) {
			u = new node(val, f, nullptr, nullptr);
			splay(u);
			return;
		}
		if (val < u -> val) insert(val, u -> lson, u);
		else if (u -> val < val) insert(val, u -> rson, u);
		else ++u -> cnt;
	}
	
	void vectorprint(vector <T> & v, node * u) {
		if (u == nullptr) return;
		vectorprint(v, u -> lson);
		for (int i = 0; i < u -> cnt; ++i) v.push_back(u -> val);
		vectorprint(v, u -> rson);
	}
	
public:
	SplayTree(){
		root = nullptr;
	}
	~SplayTree() {
		clear(root);
	}
	void insert(const T & val) {
		insert(val, root);
	}
	void vectorprint(vector <T> & data) {
		data.clear();
		vectorprint(data, root);
	}
};

